package com.zhang.leetcode;

import java.util.HashMap;
import java.util.Map;

public class LeetCode514 {

    public int findRotateSteps(String ring, String key) {
        return findRotateSteps2(ring, key, 0, new HashMap<>());
    }

    public int findRotateSteps2(String ring, String key, int count, Map<String, Integer> memo) {
        if (count == key.length()) {
            return 0;
        }

        String memoKey = ring + "_" + count;
        if (memo.containsKey(memoKey)) {
            return memo.get(memoKey);
        }

        char targetChar = key.charAt(count);
        int minSteps = Integer.MAX_VALUE;
        for (int i = 0; i < ring.length(); i++) {
            if (ring.charAt(i) == targetChar) {
                int stepsToRotate = Math.min(i, ring.length() - i);
                String nextRing = ring.substring(i) + ring.substring(0, i);
                int stepsForNextChar = 1 + stepsToRotate + findRotateSteps2(nextRing, key, count + 1, memo);
                minSteps = Math.min(minSteps, stepsForNextChar);
            }
        }

        memo.put(memoKey, minSteps);
        return minSteps;
    }

    public static void main(String[] args) {
        LeetCode514 leetCode514 = new LeetCode514();
        System.out.println(leetCode514.findRotateSteps("godding", "gd"));

    }
}
